package leetcode_2501_2600;

public class LeeCode_2552 {
    public static void main(String[] args) {
        System.out.println(countQuadruplets(new int[]{1, 3, 2, 4, 5}));
        System.out.println(countQuadruplets(new int[]{1, 2, 3, 4}));
    }
    private static long countQuadruplets(int[] nums) {
        int n = nums.length;
        int[][] great = new int[n][n + 1];
        for (int k = n - 2; k >= 0; k--){
            great[k] = great[k + 1].clone();
            for (int j = 1; j < nums[k + 1]; j++) {
                great[k][j]++;
            }
        }
        long ans = 0;
        for (int j = 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[j] > nums[k]) {
                    int x = nums[k];
                    ans += (long) (x + 1 - n + j +  great[j][x]) * great[k][nums[j]];
                }
            }
        }
        return ans;
    }
}
